package com.ry.day1129;

import java.util.Arrays;

//答案通不过，把很多答案贴上去也不对
//https://leetcode.cn/problems/cat-and-mouse/description/
public class LK913 {

    static class Solution {
        public int catMouseGame(int[][] graph) {
            //暴力解
            //return baoli(graph);
            return dp(graph);
        }

        //不贪心，就是递归+记忆化搜索
        public int dp(int[][] graph){
            int n = graph.length;
            //9: 2*8*9  再大，就是平局
            int limit =((n*(n-1))<< 1) +1;
            int[][][] dp = new int[n][n][limit];
            for (int i = 0; i <n ; i++) {
                for (int j = 0; j <n ; j++) {
                    Arrays.fill(dp[i][j],-1);
                }
            }

            return f(graph,limit,2,1,1,dp);
        }
        public int baoli(int[][] graph){
            int n=graph.length;
            boolean[][][] path = new boolean[n][n][2];
            int ans = win(graph,2,1,1,path);
            return ans;
        }

        /*
        1: 老鼠   2： 猫    3： 老鼠   4： 猫
        turn: 当前第几轮
        第turn轮要开始了！猫在cat位置，老鼠在mouse位置
        返回最终谁赢

        dp[][][] 缓存
        dp[cat][mouse][turn]=-1  这个状态之前没算过
        dp[cat][mouse][turn]=0  这个状态之前算过  平局
        dp[cat][mouse][turn]=1 这个状态之前算过  老鼠赢
        dp[cat][mouse][turn]=2 这个状态之前算过  猫赢


        limit: 固定参数  代表轮数不要超过limit ,如果超过，就算平局
         */
        public static int f(int[][] graph,
                            int limit,int cat,int mouse,int turn,
                            int[][][] dp){

            if(turn ==limit) return 0;
            if(dp[cat][mouse][turn] !=-1){
                return dp[cat][mouse][turn];
            }

            int ans =0;
            if(cat ==mouse) ans =2;
            else if(mouse ==0) ans =1;
            else {
                if((turn &1) ==1) { // 老鼠的回合  1  3  5  7  9
                    ans =2;
                    for(int next: graph[mouse]){
                        int p = f(graph,limit,cat,next,turn+1,dp);
                        ans=p==1?1:(p==0?0:ans);
                        if(ans==1){
                            break;
                        }
                    }
                }else{ //猫的回合
                    ans =1;
                    for(int next:graph[cat]){
                        if(next!=0) {
                            int p = f(graph,limit,next,mouse,turn+1,dp);
                            ans =p==2?2:(p==0?0:ans);
                            if(ans==2){
                                break;
                            }
                        }
                    }
                }
            }
            dp[cat][mouse][turn] = ans;
            return ans;
        }

        //暴力尝试
        //返回值 int   0: 平局    1： 老鼠赢   2： 猫赢
        //int[][] graph   0:{3,7,9}   1:  2:  3:{0,..} .. 7:{0,..}... 9:{0,...}
        //cat: 此时猫的位置  mouse: 老鼠此时的位置   turn: 谁的回合   等于1老鼠的回合  等于0：猫的回合
        //path路径：  当第一次出现，在老鼠的回合，猫在5位置，老鼠在7位置
        //path[cat][mouse][1] =false   如果是path[cat][mouse][0] =false 第三个坐标表示猫的回合
        //不是第一次出现 path[cat][mouse][1] =true
        public static int win(int[][] graph, int cat, int mouse, int turn, boolean[][][] path) {
            if (path[cat][mouse][turn]) { //之前来到过这个状态，平局
                return 0; //平局
            }
            //没来过
            path[cat][mouse][turn] = true;
            int ans = 0;
            if (cat == mouse) {
                ans = 2;
            } else if (mouse == 0) {
                ans = 1;
            } else {//游戏继续
                if(turn==1) { //老鼠回合
                    ans =2; //最差情况，是猫赢
                    for(int next: graph[mouse]){
                        int p=win(graph,cat,next,0,path);
                        //p的返回值如果是1，代表老鼠赢，那么最差结果ans=1,直接返回
                        ans=p==1?1:(p==0?0:ans);
                        if(ans==1){
                            break;
                        }
                    }
                }else{ //猫的回合
                    ans =1;
                    for(int next: graph[cat]){
                        if(next!=0){
                            int p = win(graph,next,mouse,1,path);
                            ans =p==2?2:(p==0?0:ans);
                            if(ans==2){
                                break;
                            }
                        }
                    }
                }

            }
            path[cat][mouse][turn] = false; //恢复现场  DFS的常规操作
            return ans;
        }
    }

    public static void main(String[] args) {

    }
}
